// https://leetcode.cn/problems/maximum-subarray/

// 题干：给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
//      子数组是数组中的一个连续部分。

// 示例：输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
//      输出：6

// 碎语：

#include <bits/stdc++.h>
using namespace std;

class Solution
{
public:
    int maxSubArray(vector<int>& nums)
    {
        // 1.状态表示
        // 2.状态转移方程
        // dp[i]表示以i位置元素为结尾的所有子数组中的最大和
        // dp[i]长度为1 nums[i] ：dp[i]长度大于1 dp[i] = max(nums[i],dp[i-1]+nums[i])

        int n = nums.size(), ret = INT_MIN;
        vector<int> dp(n); dp[0] = nums[0];

        for (int i = 1 ; i < n ; i++) dp[i] = max(nums[i], dp[i - 1] + nums[i]);
        for (int i = 0 ; i < n ; i++) ret = max(ret, dp[i]);

        return ret;
    }
};

int main()
{
    Solution sol;
    vector<int> nums = {-2,1,-3,4,-1,2,1,-5,4};

    cout << sol.maxSubArray(nums) << endl;

    return 0;
}